#ifndef STX_ALGORITHM_UNIQUE_COPY_HPP
#define STX_ALGORITHM_UNIQUE_COPY_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class BinaryPredicate, class ForwardIterator, class OutputIterator>
inline OutputIterator
unique_copy_impl(
    ForwardIterator first,
    ForwardIterator last,
    OutputIterator result,
    BinaryPredicate pred,
    std::forward_iterator_tag,
    std::output_iterator_tag)
{
    if (first != last) {
        ForwardIterator i = first;
        *result = *i;
        ++result;
        while (++first != last) {
            if (!pred(*i, *first)) {
                *result = *first;
                ++result;
                i = first;
            }
        }
    }
    return result;
}

template <class BinaryPredicate, class InputIterator, class ForwardIterator>
inline ForwardIterator
unique_copy_impl(
    InputIterator first,
    InputIterator last,
    ForwardIterator result,
    BinaryPredicate pred,
    std::input_iterator_tag,
    std::forward_iterator_tag)
{
    if (first != last) {
        *result = *first;
        while (++first != last) {
            if (!pred(*result, *first)) {
                *++result = *first;
            }
        }
        ++result;
    }
    return result;
}

template <class InputIterator, class OutputIterator, class BinaryPredicate>
inline OutputIterator
unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred)
{
    return stx::unique_copy_impl<typename add_lvalue_reference<BinaryPredicate>::type>(
        first,
        last,
        result,
        pred,
        typename std::iterator_traits<InputIterator>::iterator_category(),
        typename std::iterator_traits<OutputIterator>::iterator_category());
}

template <class InputIterator, class OutputIterator>
inline OutputIterator
unique_copy(InputIterator first, InputIterator last, OutputIterator result)
{
    typedef typename std::iterator_traits<InputIterator>::value_type v;
    return stx::unique_copy(first, last, result, equal_to<v>());
}

} // namespace stx

#endif // STX_ALGORITHM_UNIQUE_COPY_HPP
